package com.linyaonan.leetcode.sword_to_offer._41;

class MedianFinder {

    int[] arr = new int[]{};

    int mIndex = -1;

    int count = 0;

    double mid = 0D;

    /** initialize your data structure here. */
    public MedianFinder() {

    }
    
    public void addNum(int num) {
        // 首次添加
        if (count == 0) {
            arr = new int[]{num};
            count = 1;
            mIndex = 0;
            mid = num;
        } else {
            int addIndex = findAddIndex(num);
            int[] newArr = new int[arr.length + 1];
            System.arraycopy(arr, 0, newArr, 0, addIndex);
            newArr[addIndex] = num;
            if (arr.length - addIndex > 0)
                System.arraycopy(arr, addIndex, newArr, addIndex + 1, arr.length - addIndex);
            count++;
            arr = newArr;
            // 计算mIndex
            int j = (arr.length) & 1;
            // 奇数
            if (j == 1) {
                mid = arr[(arr.length) >> 1];
            } else {
                // 偶数
                int rIndex = (arr.length) >> 1;
                int lIndex = rIndex - 1;
                mid = ((double) (arr[lIndex] + arr[rIndex])) / 2;
            }
        }
    }
    
    public double findMedian() {
        if (count == 0) {
            return 0D;
        } else {
            return mid;
        }
    }

    /**
     * 通过二分法找到插入的位置
     * @param addNum
     * @return
     */
    public int findAddIndex(int addNum) {
        int l = 0;
        int r = arr.length - 1;

        while (l <= r) {
            int m = l + ((r - l) >> 1);
            int p = arr[m];
            if (addNum == p) {
                return m;
            } else {
                if (addNum < p) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
        }

        return l;
    }
}